#include<bits/stdc++.h>
using namespace std;
const int MAXN=51,MAXM=1010,INF=0x7fffffff;
int n,m,k,cnt,head[MAXN*MAXN],dis[MAXN*MAXN],ans;
bool vis[MAXN*MAXN];
struct edge
{
    int v,next,val;
}e[MAXM*MAXN*5];
queue<int> q;
void addedge(int x,int y,int z)
{
    e[++cnt]=(edge){y,head[x],z};
    head[x]=cnt;
    return;
}
void SPFA()
{
    while(!q.empty())q.pop();
    dis[1]=0;
    vis[1]=true;
    q.push(1);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=head[u];i;i=e[i].next)
        {
            int v=e[i].v;
            if(dis[v]>dis[u]+e[i].val)
            {
                dis[v]=dis[u]+e[i].val;
                if(!vis[v])
                {
                    vis[v]=true;
                    q.push(v);
                }
            }
        }
        vis[u]=false;
    }
    return;
}
int main()
{
    memset(dis,0x3f3f3f3f,sizeof(dis));
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;++i)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        for(int j=0;j<=k;++j)
        {
            addedge(x+j*n,y+j*n,z);
            addedge(y+j*n,x+j*n,z);
        }
        for(int j=0;j<k;++j)
        {
            addedge(x+j*n,y+(j+1)*n,z/2);
            addedge(y+j*n,x+(j+1)*n,z/2);
        }
    }
    SPFA();
    ans=INF;
    for(int i=1;i<=k+1;++i)
        ans=min(ans,dis[i*n]);
    printf("%d\n",ans);
    return 0;
}
